home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 17144 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: prairienet.org!wemccaug
  2. From: wemccaug@prairienet.org (Wendy E. McCaughrin)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 13 Apr 1996 22:31:03 GMT
  6. Organization: University of Illinois at Urbana
  7. Message-ID: <4kp9v7$qpd@vixen.cso.uiuc.edu>
  8. References: <4k4unk$15qe@sol.caps.maine.edu> <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca>
  9. Reply-To: wemccaug@prairienet.org (Wendy E. McCaughrin)
  10. NNTP-Posting-Host: firefly.prairienet.org
  11.  
  12.  
  13. In a previous article, slary61@maine.maine.edu (Scott) says:
  14.  
  15. >"And how would you make it faster still?" He couldn't come up with 
  16. >> >much...end of interview.
  17. >> Mybe they meant tweaking stratigies for quicksort like how
  18. >> to choose a pivot element.  Who knows. 
  19. >> 
  20. >> -- 
  21. >It's hard to beat the sort invented by Hoare at O(2log n). As far
  22. >as comparison sorts go, I don't think its been beaten.
  23. >
  24. >
  25.  Actually, the first author is very much on the right track: picking
  26.  the "right" pivot element is one of the best ways to speed Quicksort
  27.  up. Recall that, in the best case, you would like the pivot to approx-
  28.  imate the median so as to bisect the array as much as possible. In the
  29.  extreme case where you pick a minimum (or maximum) for the pivot, you
  30.  have almost as much work to do as the previous iteration/recursion.
  31.  
  32.  Of course, a second approach is to remove the recursion (much easier).
  33.  
  34.  Third, know when to stop quicksorting and start "straight" sorting
  35.  (via selection sort, e.g.) the remaining small sub-arrays. I believe
  36.  the estimates for this size range from 5 to 15.
  37.  
  38.  Fourth, consider the task of comparison itself. If "comparison"
  39.  involves something more complex than < or >, consider opportunities
  40.  for optimizing your comparison operator.
  41.  
  42.  Fifth, if the array elements are non-scalar aggregates, consider
  43.  sorting instead an "index vector" of pointers to the aggregates
  44.  to reduce the amount of data-movement entailed in partitioning 
  45.  your array.
  46.  
  47.  Sixth, if the array is very large (so that virtual memory loads
  48.  become problematical), consider sorting only sub-arrays of man-
  49.  ageable size, then merge-sorting these into the final result.
  50.  
  51.  Of course, the story by no means ends here -- just a sampler to
  52.  show how much more can be done. And of course, Hoare _is_ to be
  53.  commended upon what has turned out to be in practice a highly 
  54.  efficient algorithm, often beating heapsort.
  55.  
  56.  sjm
  57.  
  58.